// 解题思路：
// 给一个数字 n，找按照数位递增的最大数字，例如：n == 10，输出 9；n == 332，输出 299

// 暴力解法：
// 先让 i == n，判断 i 是否是按照数位递增，如果递增，返回 i，否则 i--，直到找到数字

// 贪心策略：
// 先将数字转化为字符数组 s，方便取每一个数位
// 如果 s[i] <= s[i + 1]，就让 i++，如果 i == m - 1，就表示已经遍历到最后一个字符了，所有数位都是递增的，直接返回 n 即可
// 如果 i < m - 1，就表示从 i 位置开始，后面的数位开始下降
// 数位下降就需要回退找前面和 i 位置数位数字一样的第一个位置
// 如果 s[i] == s[i - 1], i--，i 位置就是第一个要减 1 的位置 s[i]--
// 后面的数字都填上 9 即可

public class Solution {
    public int monotoneIncreasingDigits(int n) {
        StringBuilder t = new StringBuilder();
        char[] s = t.append(n).toString().toCharArray();
        int m = s.length;
        int i = 0;

        while(i + 1 < m && s[i] <= s[i + 1]) i++;
        if(i == m - 1) return n;

        while(i - 1 >= 0 && s[i] == s[i - 1]) i--;
        s[i] = (char)(s[i] - 1);

        for(int j = i + 1; j < m; j++){
            s[j] = '9';
        }
        return Integer.parseInt(new String(s));
    }
}
